# filepath: d:\Desktop\AlgorithmCode\assignment3_-group15\回溯算法：78子集\test.py
"""
78子集问题测试文件
测试回溯算法实现的正确性和性能
"""
import time
import sys
from alg import Solution
from gen import generate_test_cases

def normalize_result(result):
    """
    标准化结果，将所有子集排序以便比较
    因为题目说可以按任意顺序返回解集
    """
    # 对每个子集内部排序，然后对所有子集排序
    normalized = []
    for subset in result:
        normalized.append(sorted(subset))
    return sorted(normalized)

def test_algorithm():
    """测试算法的正确性"""
    solution = Solution()
    test_cases = generate_test_cases()
    
    print("=" * 60)
    print("78子集问题 - 算法测试")
    print("=" * 60)
    
    passed_tests = 0
    total_tests = len(test_cases)
    
    for i, case in enumerate(test_cases, 1):
        print(f"\n测试用例 {i}: {case['name']}")
        print(f"描述: {case['description']}")
        print(f"输入: {case['input']}")
        
        # 测试算法
        start_time = time.time()
        actual_result = solution.subsets(case['input'])
        end_time = time.time()
        execution_time = (end_time - start_time) * 1000  # 转换为毫秒
        
        # 标准化结果进行比较
        expected_normalized = normalize_result(case['expected'])
        actual_normalized = normalize_result(actual_result)
        
        print(f"期望结果: {case['expected']}")
        print(f"实际结果: {actual_result}")
        print(f"执行时间: {execution_time:.2f} ms")
        
        # 验证结果
        if expected_normalized == actual_normalized:
            print("✓ 测试通过")
            passed_tests += 1
        else:
            print("✗ 测试失败")
            print(f"期望标准化: {expected_normalized}")
            print(f"实际标准化: {actual_normalized}")
        
        print("-" * 50)
    
    # 打印测试总结
    print(f"\n{'='*60}")
    print("📊 测试结果总结")
    print(f"{'='*60}")
    print(f"通过测试: {passed_tests}")
    print(f"失败测试: {total_tests - passed_tests}")
    print(f"总测试数: {total_tests}")
    print(f"成功率: {passed_tests/total_tests*100:.1f}%")
    
    if passed_tests == total_tests:
        print("🎉 所有测试通过！算法实现正确")
    else:
        print(f"⚠️  有 {total_tests - passed_tests} 个测试失败，请检查算法实现")
    
    return passed_tests == total_tests

def performance_test():
    """性能测试"""
    solution = Solution()
    
    print(f"\n{'='*60}")
    print("⚡ 性能测试")
    print(f"{'='*60}")
    
    test_sizes = [3, 5, 7, 8, 9, 10]
    
    for size in test_sizes:
        nums = list(range(1, size + 1))
        
        # 预热
        solution.subsets(nums)
        
        # 正式测试
        times = []
        for _ in range(5):
            start_time = time.time()
            result = solution.subsets(nums)
            end_time = time.time()
            times.append((end_time - start_time) * 1000)
        
        avg_time = sum(times) / len(times)
        expected_subsets = 2 ** size
        actual_subsets = len(result)
        
        print(f"测试规模: {size} 个元素")
        print(f"期望子集数: {expected_subsets}")
        print(f"实际子集数: {actual_subsets}")
        print(f"平均执行时间: {avg_time:.2f} ms")
        
        # 性能评估
        if avg_time < 1:
            performance = "优秀"
        elif avg_time < 10:
            performance = "良好"
        elif avg_time < 100:
            performance = "一般"
        else:
            performance = "需要优化"
        
        print(f"性能评估: {performance}")
        print("-" * 40)

def verify_complexity():
    """验证时间复杂度"""
    solution = Solution()
    
    print(f"\n{'='*60}")
    print("📈 复杂度验证")
    print(f"{'='*60}")
    
    print("理论分析:")
    print("- 时间复杂度: O(n * 2^n)")
    print("- 空间复杂度: O(2^n)")
    print("- 对于大小为n的数组，应该生成2^n个子集")
    print()
    
    for n in range(1, 8):
        nums = list(range(1, n + 1))
        result = solution.subsets(nums)
        expected_count = 2 ** n
        actual_count = len(result)
        
        print(f"n={n}: 期望{expected_count}个子集, 实际{actual_count}个子集 " + 
              ("✓" if expected_count == actual_count else "✗"))

def main():
    """主测试函数"""
    print("开始78子集问题测试...\n")
    
    # 算法正确性测试
    correctness_passed = test_algorithm()
    
    if correctness_passed:
        # 性能测试
        performance_test()
        
        # 复杂度验证
        verify_complexity()
    
    print(f"\n{'='*60}")
    print("测试完成")
    print(f"{'='*60}")

if __name__ == "__main__":
    main()